#include <list>
#include <time.h>
#include <cstdio>
#include <cstdlib>
#include <iostream>

typedef std::list<unsigned int> intlist;

intlist merge_lists(intlist *lists, unsigned int k) {
    intlist merged;
    
    do {
        int m = -1; // list index with largest element
        for (unsigned int i = 0; i < k; i++) {
            if (lists[i].empty()) continue; // skip list if already empty
            
            if (m < 0) m = i; // first list we see...
            else if (lists[i].front() > lists[m].front()) // check first element of subsequent list
                m = i;
        }
        
        if (m < 0) break; // all lists were empty, done
        
        merged.push_back(lists[m].front()); // append largest element to results
        lists[m].pop_front(); // remove largest element from list
    } while (true);
    
    return merged;
}


intlist reverse_list(intlist list) {
    intlist reversed;

    for (intlist::reverse_iterator rit = list.rbegin(); rit != list.rend(); ++rit) {
        reversed.push_back(*rit);
    }
    return reversed;
}

/**
 * returns a list sorted from max to min
**/
intlist* generate_sorted_lists(int amountOfLists, int listElements) {
    intlist* lists = new intlist[amountOfLists];

    for (int i = 0; i < amountOfLists; ++i) {
        for (int j = 0; j < listElements; ++j) {
            if (j == 0) {
                // pushback random number in range of 0...9
                lists[i].push_back(rand() % 10);
            } else {
                // push_back random number + last number to get a sorted list
                lists[i].push_back(lists[i].back() + rand() % 10);
            }
        }
        lists[i] = reverse_list(lists[i]);
    }

    return lists;
}

int main(int argc, char* argv[]) {
    /* initialize random seed: */
    srand ( time(NULL) );

 
    const int amountOfLists = 5;
    const int listElements = 50;

    intlist* lists = generate_sorted_lists(amountOfLists, listElements);

    intlist merged = merge_lists(lists, amountOfLists);

    for (intlist::iterator it = merged.begin(); it != merged.end(); ++it) {
        printf("%d\n", *it);
    }

	return 0;
}